/* 图的邻接矩阵存储 */


int MaxSize = 100;

template <typename DataType>
class MGraph
{
public:
    MGraph(DataType a[], int n, int e); // 构造函数
    ~MGraph();  // 析构函数
    void DETraverse(int v);     // 深度优先遍历
    void BFTraverse(int v);     // 广度优先遍历
    void Dijkstra(int v);   // Dijkstra算法求最短路
    void Floyd(int v);      // Floyd算法求最短路
private:
    DataType vertex[MaxSize];   // 存储顶点的数组
    int edge[MaxSize][MaxSize]; // 存储边的数组
    int vertexNum, edgeNum;     // 顶点数和边数
};

// 构造函数（初始化邻接矩阵）
template <typename DataType>
MGraph<DataType>::MGraph(DataType a[], int n, int e)
{
    int i,j,k;
    vertexNum = n; edgeNum = n;
    for (i = 0; i<vertexNum ; i++)
        vertex[i] = a[i];               // 初始化邻接矩阵
    for(i = 0 ; i<vertexNum ; i++)
        for (j = 0; j < vertexNum; j++)
            edge[i][j] = 0;             // 依次输入每条边
    for(k = 0; k<edgeNum; k++)
    {
        std::cin >> i >> j;             // 输入边依附的两个顶点编号
        edge[i][j] = 1; edge[j][i] = 1; // 有边标志
    }
}

// 深度优先遍历
template <typename DataType>
void MGraph<DataType>::DETraverse(int v)
{
    std::cout << vertex[v]; // 输入初始顶点序号
    visited[v] = 1;         // 将v设为已被遍历
    // 递归调用函数，不断输入邻接点
    for(int j = 0; j < vertexNum ; j++)     // 对图中所有顶点循环
        if(edge[v][j] == 1 && visited[j] == 0)  // 若该点与当前点邻接，且未被遍历
            DETraverse(j);      
}


// 广度优先遍历
template <typename DataType>
void MGraph<DataType>::BFTraverse(int v)
{
    int w, j Q[MaxSize];        // 采用顺序队列
    int front = -1 , rear = -1; // 初始化队列
    cout << vertex[v];
    visited[v] = 1;
    Q[++rear] = v;              // 被访问顶点入队
    while(front != rear)        // 当队列非空时
    {
        w = Q[++front];         // 将队头元素出队，并送到v中
        for(j = 0; j< vertexNum; j++)
            if(edge[w][j] == 1 && visited[j] == 0)  // 若与当前点邻接，且还未被遍历过，则将其入队
            {
                cout << vertex[j]; visited[j] = 1; Q[++rear] = j;
            }
    }
}

// Dijkstra算法（MGraph的函数）
template <typename DataType>
void MGraph<DataType>::Dijkstra(int v)    // 从源点v出发
{
    int i,k, num, dist[MaxSize];
    string path[MaxSize];
    for(i = 0 ; i < vertexNum; i++)             // 初始化数组dist和path
    {
        dist[i] = edge[v][i];       
        if(dist != 100)                         // 假设100为边上权的最大值
            path[i] = vertex[v] + vertex[i];    // 将字符串连接
        else
            path[i] = "";
    }
    for(num = 1; num < vertexNum; num++)
    {
        k = Min(dist, vertexNum);           // 在dist数组中找最小值，并返回下标
        std::cout << path[k] << dist[k];    // 
        for(i = 0; i < vertexNum; i++)      // 修改数组dist和path
            if(dist[i] > dist[k] + edge[k][i])
            {
                dist[i] = dist[k] + edge[k][i];
                path[i] = path[k] + vertex[i];  // 字符串连接
            }
        dist[k] = 0;     // 将顶点k加入集合S
    }
}

// Floyd算法

template <typename DataType>
void MGraph<DataType>::Floyd(int v)   // 从源点v出发
{
    int i, k , num , dist[MaxSize][MaxSize];
    string path[MaxSize][MaxSize];
    // 变量初始化（共n^2次）
    for (i = 0 ; i < vertexNum; i++)
        for (j = 0; j < vertexNum; j++)
        {
            // 初始化dist
            dist[i][j] = edge[i][j];
            // 初始化path
            if(dist[i][j] != 100)       // 设100为权的最大值
                path[i][j] = vertex[i] + vertex[j];
            else
                path[i][j] = "";
        }
    // 进行n次迭代
    for (k = 0; k < vertexNum; k++)
        for (i = 0; i < vertexNum; i++)
            for(j = 0; j<vertexNum; j++)
                if(dist[i][k] + dist[k][j] < dist[i][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = path[i][k] + path[k][j];
                }
}